package br.unicamp.integralization.dp;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

import br.unicamp.integralization.dto.Allocation;
import br.unicamp.integralization.dto.History;
import br.unicamp.integralization.dto.Subject;
import br.unicamp.integralization.dto.SubjectGroup;

public class PotaSolver {
	public static final int NAO_ALOCADO = -2;
	public static final int EXTRA_CURRICULAR = -1;

	public static History history;

	public static List<Subject> disciplinasObrigatorias = new ArrayList<Subject>();
	public static List<Subject> disciplinasEletivas = new ArrayList<Subject>();

	public static List<SubjectGroup> gruposEletivas = new ArrayList<SubjectGroup>();

	public static int[] associacoes;
	public static int[] somaCreditos;

	public static HashSet<String> estadosAvaliados = new HashSet<String>();

	public static int alocacaoMaisProxima;

	public static Allocation melhorAlocacao;

	private static void setup() {
		disciplinasObrigatorias = new ArrayList<Subject>();
		disciplinasEletivas = new ArrayList<Subject>();
		gruposEletivas = new ArrayList<SubjectGroup>();
		estadosAvaliados = new HashSet<String>();
		alocacaoMaisProxima = 0;
		melhorAlocacao = null;
	}

	public static Allocation execute(History history) {
		setup();

		PotaSolver.history = history;
		Allocation catalogo = history.getAllocation();

		for (Subject disciplinaCursada : history.getSubjects()) {

			boolean obrigatoria = false;
			for (Subject disciplinaObrigatoria : catalogo
					.getMandatorySubjects().getSubjects()) {
				if (disciplinaCursada.matches(disciplinaObrigatoria)) {
					PotaSolver.disciplinasObrigatorias.add(disciplinaCursada);
					obrigatoria = true;
					break;
				}
			}
			if (!obrigatoria) {
				PotaSolver.disciplinasEletivas.add(disciplinaCursada);
			}
		}

		int totalCatalogo = 0;
		for (SubjectGroup grupoEletivas : catalogo.getElectiveGroups()) {
			totalCatalogo += grupoEletivas.getCredits();
			PotaSolver.gruposEletivas.add(grupoEletivas);
		}

		int creditosAlocadosEmCadaGrupo[] = new int[gruposEletivas.size()];

		somaCreditos = new int[disciplinasEletivas.size()];

		for (int c = 0; c < disciplinasEletivas.size(); c++) {

			if (c > 0) {
				PotaSolver.somaCreditos[c] += PotaSolver.somaCreditos[c - 1];
			}

			PotaSolver.somaCreditos[c] += disciplinasEletivas.get(c)
					.getCredits();
		}

		associacoes = new int[disciplinasEletivas.size()];

		for (int c = 0; c < disciplinasEletivas.size(); c++) {
			associacoes[c] = NAO_ALOCADO;
		}

		boolean t = tenta(0, creditosAlocadosEmCadaGrupo, totalCatalogo);

		if (!t) {
			return null;
		}

		Allocation alloc = createAllocation(history, disciplinasObrigatorias,
				associacoes);

		return alloc;
	}

	private static boolean tenta(int i, int[] creditosAlocadosEmCadaGrupo,
			int creditosRestantes) {

		// System.out.println("Tentando " + i + " de " +
		// String.valueOf(disciplinasEletivas.size()-1));

		if (alocacaoMaisProxima > creditosRestantes) {
			alocacaoMaisProxima = creditosRestantes;
			melhorAlocacao = createAllocation(history, disciplinasObrigatorias,
					associacoes);
		}

		// Se os créditos restantes atingem 0, o aluno se formou
		if (creditosRestantes <= 0) {
			return true;
		}

		// Se i é inviável
		String hash = createHashKey(i, creditosAlocadosEmCadaGrupo);

		if (i >= disciplinasEletivas.size()
				|| inviavel(i, creditosAlocadosEmCadaGrupo, creditosRestantes)
				|| estadosAvaliados.contains(hash)) {
			estadosAvaliados.add(hash);// guarda estado
			return false;
		}

		boolean achou = false;

		Subject disciplinaI = disciplinasEletivas.get(i);

		for (int c = 0; c < gruposEletivas.size(); c++) {
			if (gruposEletivas.get(c).matches(disciplinaI)
					&& achou == false
					&& creditosAlocadosEmCadaGrupo[c] < gruposEletivas.get(c)
							.getCredits()) {
				associacoes[i] = c;// a disciplina i esta alocada no grupo c

				int delta = Math.min(gruposEletivas.get(c).getCredits()
						- creditosAlocadosEmCadaGrupo[c],
						disciplinaI.getCredits());
				creditosRestantes -= delta;

				creditosAlocadosEmCadaGrupo[c] += disciplinaI.getCredits();

				achou = tenta(i + 1, creditosAlocadosEmCadaGrupo,
						creditosRestantes);

				if (achou) {
					return true;
				}

				creditosRestantes += delta;
				associacoes[i] = NAO_ALOCADO;
				creditosAlocadosEmCadaGrupo[c] -= disciplinaI.getCredits();
			}
		}

		if (associacoes[i] == NAO_ALOCADO && achou == false) {
			associacoes[i] = EXTRA_CURRICULAR;
			achou = tenta(i + 1, creditosAlocadosEmCadaGrupo, creditosRestantes);
			associacoes[i] = NAO_ALOCADO;
		}

		if (achou == false) {
			estadosAvaliados.add(hash);// guarda estado
		}
		return false;
	}

	private static String createHashKey(int index,
			int[] creditosAlocadosEmCadaGrupo) {
		StringBuilder str = new StringBuilder();
		str.append(index);

		for (int i = 0; i < creditosAlocadosEmCadaGrupo.length; i++) {
			str.append(",");
			str.append(creditosAlocadosEmCadaGrupo[i]);
		}

		return str.toString();
	}

	// Existem duas situações que tornam uma alocação inviável:
	// 1) Se o total de créditos que precisam ser alocados é maior dos que
	// restam para alocar
	// 2) Se algum dos grupos de eletivas não têm mais como ser preenchido com
	// as matérias que restam pra alocar
	private static boolean inviavel(int i, int[] creditosAlocadosEmCadaGrupo,
			int creditosRestantes) {
		int totalCreditosQueAindaPodemSerAlocados = somaCreditos[disciplinasEletivas
				.size() - 1];
		if (i > 0) {
			totalCreditosQueAindaPodemSerAlocados -= somaCreditos[i - 1];
		}

		if (creditosRestantes > totalCreditosQueAindaPodemSerAlocados) {
			return true;
		}

		for (int c = 0; c < gruposEletivas.size(); c++) {
			SubjectGroup grupoEletiva = gruposEletivas.get(c);
			int alocado = creditosAlocadosEmCadaGrupo[c];

			for (int j = i; j < disciplinasEletivas.size(); j++) {
				if (grupoEletiva.matches(disciplinasEletivas.get(j))) {
					alocado += disciplinasEletivas.get(j).getCredits();
				}
			}

			if (alocado < grupoEletiva.getCredits()) {
				return true;
			}
		}

		return false;
	}

	public static Allocation createAllocation(History history,
			List<Subject> mandatoryDone, int[] allocatedSubjects) {
		Allocation allocation = new Allocation();

		List<SubjectGroup> electiveGroups = allocation.getElectiveGroups();

		for (int i = 0; i < history.getAllocation().getElectiveGroups().size() + 1; i++) {
			electiveGroups.add(new SubjectGroup());
		}

		System.out.println("disciplinasEletivas.size(): "
				+ disciplinasEletivas.size());
		System.out.println("allocatedSubjects.length: "
				+ allocatedSubjects.length);
		for (int i = 0; i < disciplinasEletivas.size(); i++) {
			Subject subject = disciplinasEletivas.get(i);
			if (allocatedSubjects[i] != NAO_ALOCADO
					&& allocatedSubjects[i] != EXTRA_CURRICULAR) {

				electiveGroups.get(allocatedSubjects[i]).addCatalogueSubject(
						subject);
			} else {
				System.out.println("??? " + allocatedSubjects[i]);
				electiveGroups.get(electiveGroups.size() - 1)
						.addCatalogueSubject(subject);
			}
		}

		allocation.getMandatorySubjects().getSubjects().addAll(mandatoryDone);

		return allocation;
	}
}
